package zhengqc.tree;

import zhengqc.list.ArrayList;

public class BSTree<E extends Comparable<E>> extends AbstractBSTree<E> {
    public BSTree() {
        this.root = null;
        this.size = 0;
        this.tempList = new ArrayList<>();
        tempElement = null;
    }
    /* 向以 node 为根节点的二分搜索树中插入元素 element, 返回插入新节点后的二分搜索树的根节点 */
    private Node addNode(Node node, E element) {
        if (node == null) {
            ++ this.size;
            return new Node(element);
        }
        if (element.compareTo(node.element) < 0) {
            node.left = addNode(node.left, element);
        } else if (element.compareTo(node.element) > 0) {
            node.right = addNode(node.right, element);
        } else {
            // 相当于不做操作
            node.element = element;
        }
        return updateNode(node);
    }
    @Override /* 向二分搜索树插入元素 */
    public void add(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element is null!");
        }
        this.root = addNode(this.root, element);
    }

    /* 删除以 node 为根的二分搜索树中值为 element 的节点; 返回删除节点后新的二分搜索树的根节点 */
    private Node removeNode(Node node, E element) {
        // 未找到值为 element 的节点
        if (node == null) {
            return null;
        }
        Node retNode = null;
        if (element.compareTo(node.element) < 0) {
            node.left = removeNode(node.left, element);
            retNode = node;
        } else if (element.compareTo(node.element) > 0) {
            node.right = removeNode(node.right, element);
            retNode = node;
        } else {
            // 先保存带删除的节点值
            this.tempElement = node.element;
            if (node.left == null) { // 待删除节点左子树为空
                -- this.size;
                retNode = node.right;
            } else if (node.right == null) { // 待删除节点右子树为空
                -- this.size;
                retNode = node.left;
            } else {
                // 待删除节点的左右子树均不为空
                // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点, 用这个节点代替待删除节点的位置
                Node successor = getMinimumNode(node.right);
                successor.right = removeMinimumNode(node.right);
                successor.left = node.left;
                retNode = successor;
            }
        }
        return updateNode(retNode);
    }
    @Override /* 从二分搜索树中删除指定元素; 原则上不需要返回值, 仅供特殊需求, 如实现 Map */
    public E remove(E element) {
        this.tempElement = null;
        this.root = removeNode(this.root, element);
        return this.tempElement;
    }

    /* 删除以 node 为根节点的二分搜索树中的最小节点; 返回删除节点后新的二分搜索树的根节点 */
    private Node removeMaximumNode(Node node) {
        if (node.right == null) {
            -- this.size;
            this.tempElement = node.element;
            return node.left;
        }
        node.right = removeMaximumNode(node.right);
        return node;
    }
    @Override /* 删除二分搜索树中最大的元素, 并返回 */
    public E removeMaximum() {
        this.tempElement = null;
        if (this.isEmpty()) {
            throw new IllegalArgumentException("BSTree is empty");
        }
        this.root = removeMaximumNode(this.root);
        return this.tempElement;
    }

    /* 删除以 node 为根节点的二分搜索树中的最小节点; 返回删除节点后新的二分搜索树的根节点 */
    private Node removeMinimumNode(Node node) {
        if (node.left == null) {
            -- this.size;
            this.tempElement = node.element;
            return node.right;
        }
        node.left = removeMinimumNode(node.left);
        return node;
    }
    @Override /* 删除二分搜索树中最小的元素, 并返回 */
    public E removeMinimum() {
        this.tempElement = null;
        if (this.isEmpty()) {
            throw new IllegalArgumentException("BSTree is empty");
        }
        this.root = removeMinimumNode(this.root);
        return this.tempElement;
    }
    private Node updateNode(Node node) {
        // 对于删除, 须有此条件判断; 对于添加, 则可有可无
        if (node == null) {
            return null;
        }
        // 更新 node 的 height
        node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
        return node;
    }
}
